
// leetcode 35. 搜索插入位置
//class Solution {
//    public int searchInsert(int[] nums, int target) {
//        int left = 0, right = nums.length - 1;
//        while (left <= right) {
//            int mid = (left + right) / 2;
//            if (nums[mid] > target) {
//                right = mid - 1;
//            } else if (nums[mid] < target) {
//                left = mid + 1;
//            } else {
//                return mid;
//            }
//        }
//        return left;
//    }
//}

// leetcode 74. 搜索二维矩阵
//class Solution {
//    public boolean searchMatrix(int[][] matrix, int target) {
//        int m = matrix.length, n = matrix[0].length;
//        int x = 0, y = n - 1;
//        while (x < m && y >= 0) {
//            if (matrix[x][y] > target) {
//                y--;
//            } else if (matrix[x][y] < target) {
//                x++;
//            } else {
//                return true;
//            }
//        }
//        return false;
//    }
//}


// leetcode 34. 在排序数组中查找元素的第一个和最后一个位置
//class Solution {
//    public int[] searchRange(int[] nums, int target) {
//        if (nums == null || nums.length == 0)
//            return new int[]{-1, -1};
//        // 找最左边的 target 和最右边的 target
//        int left = 0, right = nums.length - 1;
//        while (left <= right) {
//            int mid = (left + right) / 2;
//            if (nums[mid] < target) {
//                left = mid + 1;
//            } else {
//                right = mid - 1;
//            }
//        }
//
//        // 此时 left 就是最左边的下标
//        int i = left;
//        right = nums.length - 1;
//        // 3 3 3 3 4 5
//        while (left <= right) {
//            int mid = (left + right) / 2;
//            if (nums[mid] > target) {
//                right = mid - 1;
//            } else {
//                left = mid + 1;
//            }
//        }
//        if (i < left)
//            return new int[]{i, left - 1};
//        return new int[]{-1, -1};
//    }
//}

// leetcode 33. 搜索旋转排序数组
//class Solution {
//    public int search(int[] nums, int target) {
//        int left = 0, right = nums.length - 1;
//        int key = nums[right];
//        while (left < right) {
//            int mid = (left + right) / 2;
//            if (nums[mid] > key) {
//                left = mid + 1;
//            } else {
//                right = mid;
//            }
//        }
//
//        int i = 0, j = left - 1, k = left;
//        right = nums.length - 1;
//        while (i <= j) {
//            int mid = (i + j) / 2;
//            if (nums[mid] > target) {
//                j = mid - 1;
//            } else if (nums[mid] < target) {
//                i = mid + 1;
//            } else {
//                return mid;
//            }
//        }
//
//        while (k <= right) {
//            int mid = (k + right) / 2;
//            if (nums[mid] > target) {
//                right = mid - 1;
//            } else if (nums[mid] < target) {
//                k = mid + 1;
//            } else {
//                return mid;
//            }
//        }
//        return -1;
//    }
//}